"""
题目：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
思路：使用双指针.让pa=headA,pb=headB,只要pa!=pb，就不断移动指针，当pa为None时，就让其指向headB,同理，pb为none时，让其只想headA，如果二者相等，则返回节点，否则返回None。
时间复杂度：O(m + n)
空间复杂度：O(1)
"""
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        pA,pB = headA,headB
        while pA != pB:
            pA = pA.next if pA is not None else headB
            pB = pB.next if pB is not None else headA
        return pA